package main

import (
	"fmt"
	"sort"
)


func main()  {
	nums:=[]int{12,2,3}
	nums1:=permute(nums)
	fmt.Println(nums1)
}

func permute(nums []int) [][]int {
	sort.Ints(nums)
	// 回溯
	res := [][]int{}

	var backTrack func(path []int, start int)
	// 回溯的经典模式，已访问路径，当前节点
	backTrack = func(path []int, start int) {

		if len(path) == len(nums) {
			// 把path添加到reszhong
			tmp := make([]int, len(path))
			// copy函数的使用		
			copy(tmp ,path)
			res = append(res, tmp)
			return
		}

		for i := start; i < len(nums); i++ {
			// 如果当前路径包含相同字母，不添加
			flag := false
			for _, v := range path {
				if v == nums[i] {
					flag = true
				}
			}
			if flag {
				continue
			}
			
			path = append(path, nums[i])
			backTrack(path, start)
			path = path[:len(path) - 1]
		}

	}
	backTrack([]int{}, 0)
	return res
}


func permute2(nums []int) [][]int {
    // 很基础的题，很多扩展题都有此而来
    // 可以使用深搜
    // 要非常熟练
    // 1,思路很清晰，2，程序语法很熟练
	// 错的很奇怪
    res:=[][]int{}
    if len(nums)==0{
        return res
    }
    if len(nums)==1{
        res =append(res,[]int{nums[0]})
		return res
    }
	
	// 代码的行为，让我有点看不懂
	// 对slice的底层
    for i:=0;i<len(nums);i++{
		// 当i=1时
	
        nums_new :=make([]int,0)
		nums_new=append(nums_new,nums[0:i]...)
		nums_new =append(nums_new,nums[i+1:]...)
		if i==1{
			fmt.Println("----nums",nums)
			fmt.Println("----",nums_new)
		}
		// TODO: nums_new使用了nums的空间，大bug
        // nums_new =append(nums_new,nums[i+1:]...)
    	if i==1{
			fmt.Println(nums_new)
		}
        res1:=permute2(nums_new)
        for _,val:=range res1{
            val2:=[]int{nums[i]}
            val2 = append(val2,val...)
            res= append(res,val2)
        }  
    }
    return res
}